/**
 * @param {string} s
 * @param {number} repeatLimit
 * @return {string}
 */
 var repeatLimitedString = function(s, repeatLimit) {
  const mp = new Map()
  for(let ch of s) {
    mp.set(ch, (mp.get(ch) ?? 0) + 1)
  }
  const pq = new PriorityQueue((a,b) => a[0] > b[0])
  for(let [ch, cnt] of mp) {
    pq.push([ch, cnt])
  }
  let ans = ''
  let pre = '', preCnt = 0
  while(pq.size) {
    let [ch, cnt] = pq.pop()
    if(ch === pre && preCnt === repeatLimit){
      if(pq.size){
        let [ch1, cnt1] = pq.pop()
        ans += ch1
        pre = ch1, preCnt = 1
        if(cnt1 - 1 > 0) pq.push([ch1, cnt1-1])
      }else break
    }else {
      let len = Math.min(cnt, repeatLimit)
      ans += ch.repeat(len)
      cnt -= len
      pre = ch, preCnt = len
    }
    if(cnt > 0) {
      pq.push([ch, cnt])
    }
  }
  return ans
};

class PriorityQueue {
  // 默认最大堆
  constructor(
    compare = (a, b) => a > b 
    ){
    this.data = []
    this.size = 0
    this.compare = compare
  }

  peek() {
    return this.size === 0 ? null : this.data[0] 
  }

  push(val) {
    this.data.push(val)
    this._shifUp(this.size++)
  }

  pop() {
    if(this.size === 0) { return null }
    this._swap(0, --this.size)
    this._shifDown(0)
    return this.data.pop()
  }

  _parent(index) {
    return index - 1 >> 1
  }
  
  _child(index) {
    return (index << 1) + 1
  }

  _shifDown(index) {
    while(this._child(index) < this.size) {
      let child = this._child(index)
      if(child + 1 < this.size 
        && this.compare(this.data[child + 1], this.data[child])) {
          child = child + 1
      }
      if(this.compare(this.data[index], this.data[child])){
        break
      }
      this._swap(index, child)
      index = child
    }
  }

  _shifUp(index) {
    while(this._parent(index) >= 0 
    && this.compare(this.data[index], this.data[this._parent(index)])) {
      this._swap(index, this._parent(index))
      index = this._parent(index)
    }
  }

  _swap(a, b) {
    [this.data[a], this.data[b]] = [this.data[b], this.data[a]]
  }
}
